A digital data processing system includes three basic elements, namely, a processor, a memory and an input/output system. The memory stores information in addressable storage locations. This information includes data and instructions for processing the data. The processor fetches information from the memory, interprets the information as either an instruction or data, processes the data in accordance with the instructions, and returns the processed data to the memory for storage therein. The input/output system control of the processor, also communicates with the memory element to transfer information, including instructions and data to be processed, to the memory, and to obtain processed data from the memory. Typically, the input/output system includes a number of diverse types of units, including video display terminals, printers, interfaces to the public telecommunications network, and secondary storage subsystems, including disk and tape storage devices.
Instructions processed by the processor are organized into one or more programs, each of which is executed in the context of a "process". A modern digital computer system typically can execute a plurality of processes concurrently. For example, a modern computer system may execute, in an interleaved fashion, a predetermined maximum number of processes each generally for selected amounts of time. At the end of a process's processing time, the computer system will stop processing that process and begin processing another process. A computer system may terminate processing of a particular process if the process, for example, requests an input/output operation, such as a transfer to or from a disk unit. Since, when a process requests such an input/output operation, the computer system typically waits until the completion of the input/output operation before it resumes processing the process that requested the input/output operation, and since an input/output operation typically can take a considerable amount of time, relative to the time required for the computer system to execute instructions, the computer switches to another process when a process that is currently executing requests an input/output operation. While, with this "multi-programming" facility, the computer system may take longer to process each individual program, since the program's process is only executed during its assigned time slots, it will be appreciated that multiprogramming does permit the computer system to process a plurality of programs in less total time, at least in part because the computer system is not stalled waiting for input/output operations to complete.
Multi-programming also provides other advantages, most notably that a number of process may share and concurrently process, in a regulated manner, data stored in shared storage devices, such as, for example, disk storage units. To enhance the security of data, that is, to reduce the likelihood that data can be read or altered by unauthorized processes, computer systems often provide extensive security facilities for regulating access to particular data files by the various processes.
However, secrecy of data in digital computer systems may be threatened by covert transmission of data between cooperating processes. For example, a process which has access to high-secrecy data may transmit the data to a process which is not authorized to read the disk files which contain the data. This may be accomplished by a "Trojan horse" in the process having access to the high-secrecy data (the "high-secrecy process") controlling various resources in the computer systems which it shares with the other process, identified as the "spy process." The "Trojan horse" is a clandestine program in the high-secrecy process which is unknown to the user of other programs in the high-secrecy process, and both it and the spy process can manipulate and observe the conditions of the shared resources. The shared resources thereby provide "channels" which can be used by the Trojan horse and the spy process to facilitate the covert transmission of high-secrecy information to the other process which would otherwise not have access to it.
Two general types of covert channels have been identified in computer systems, namely, timing channels and storage channels. Timing channels may arise as a result of the availability or unavailability of particular system resources during particular time intervals. For example, some types of instructions cause the processor to test system resources, such as interlocks, to determine whether they are set or cleared. Some such instructions may, for example, enable the processor to test the condition of an interlock to determine whether it is set, and, if not, set the interlock and perform some other operation. On the other hand, if, upon testing the condition of the interlock, the processor determines that the interlock is set, the processor stalls until the interlock is later cleared. Others of such instructions enable the processor to clear the interlock. Thus, if a program executing in one processor issues an instruction that enables the processor to set an interlock, while the interlock is set, another process executing another program will stall if it attempts to execute a similar instruction, until the interlock is cleared by the program in the first processor. A Trojan horse in one processor may thus transmit data by varying the rate at which it enables the processor to set the interlocks, and the spy process may determine the values of the data by determining the rates, at various times, at which it can concurrently enable the processor to execute instructions which would also set the interlock.
The bandwidth, that is, the rate at which a Trojan horse in one process can transmit data to a spy process is directly related to the accuracy and precision with which the processes can determine timing intervals. If both the Trojan horse and the spy process can accurately and precisely measure timing intervals, they can transmit data, using the above-described interlocked instruction mechanism, for example, at a relatively high rate. On the other hand, as the accuracy and precision with which either process can determine timing intervals diminish, so does the bandwidth of a covert timing channel.
A typical digital computer system includes a number of sources of timing information from which a process may identify the duration of a timing interval. Most notably, a typical digital computer system includes at least one system clock, that is maintained and regularly incremented by the operating system, whose value a process can obtain. Thus, on a multiprocessor, for example, a spy process on one processor may, immediately prior to beginning execution of interlocked instructions as described above, obtain the value of the system clock, thereafter begin executing the interlock instructions, and, after executing a predetermined number of the interlock instructions, obtain the value of the system clock at that point. The spy process may then determine the time interval required to process the interlocked instructions by determining the difference between the two system clock values and, from that, the value of a data bit controlled by the Trojan horse program in another processor. A timing channel is identified by the particular mechanism used by the Trojan horse to vary the rate of processing of the spy process, and a timing channel exploitation relates to the procedure of transmitting information by using one of the timing channels and one of the particular sources of timing information.
A spy process can identify a timing interval, with reference to other operations in the computer system. For example, as described above, a typical multiprogramming computer system processes a plurality of processes, which may include a spy process, in interleaved time slots. If the time slots are of predictable duration, a spy process may use the time slot itself as a time interval. In addition, a spy process can issue a series of input/output requests, such as transfers to or from mass storage subsystems, such as disk or tape storage devices, or to or from terminals, printers, or various network interfaces, which will be completed at periodic intervals. When an input/output operation initiated by a process is completed, the operating system typically interrupts it to notify it of the completion. Since the spy process initiated the input/output operations to complete at periodic intervals, the operating system will supply the interrupts at periodic intervals, and so the spy process can use the interrupts to define the timing interval.
Even if the operating system does not supply the interrupts at periodic intervals, if, for example, an input/output operation enables a disk storage subsystem to transfer data to a specified buffer, which the spy process identified in the input/output request, the spy process can iteratively test the contents of the buffer to determine when the disk storage subsystem has begun loading the data into the buffer, and determine the required interval from that. In addition, some disk storage subsystems signal completion of a storage request by generating a completion packet identifying the status of the operation and transmitting it to the process that requested the disk storage operation, and a spy process can use the timing with which it receives a series of completion packets to define timing intervals.
A process can also determine timing information in other ways. If, for example, a process issues a write request to enable a series of characters to be written to a terminal device, and follows it immediately with a cancel request, the process can identify the interval between the time the operating system initiated the write operation and the time it recognized the cancel request by reading the contents of the terminal device's screen buffer and counting the number of characters. Since a computer system transmits the characters on a periodic basis, the number of characters identifies the length of time between when the operating system began and ended character transmission.
Similarly, two processes being processed by different nodes, each comprising a computer system, over a network in a distributed digital data processing system, may determine timing of a timing interval. If one process periodically transmits characters over the network to the other process, since the network transmits characters at a periodic, and generally known, rate, the other process can derive timing information from the rate at which it receives the characters.
Many of these techniques may provide a process with timing information that may be somewhat less precise than it might obtain by obtaining the value of the system clock from the operating system, but they would all permit a spy process, executing the interlocked instructions as described above, or performing other operations whose speed can be influenced by the high-secrecy process, to obtain timing interval information that is sufficiently accurate to enable it to determine values of bits in a data stream as described above of a relatively large bandwidth.